퀵정렬 {quick sort}
https://choiwheatley.notion.site/quick-sort-8720f36d603840f1b37fa73465c76eb0
TL;DR
- 퀵정렬은 분할정복의 예시 중 유명한 알고리즘으로, 병합정렬의 분할 후 정복 개념과는 달리 정복 후 분할 정책을 사용한다.
- 먼저 시퀀스를 두 부분으로 나누는 파티션 작업을 통해 피벗의 위치를 고정시킨다. 그리고 재귀호출을 사용하여 피벗의 왼쪽과 오른쪽에 대한 정렬을 각기 수행한다.
- 피벗의 위치는 맨앞, 맨뒤, 정 가운데, 랜덤, 중앙값으로 잡는 방법이 있고, 아래 수도코드는 랜덤으로 인덱스를 잡아 end로 보낸 뒤 파티셔닝을 수행한다.
Pseudo Code
유튜브 영상에서 보던 방식과는 조금 달라서 헤맸다. 실제 코드를 보면 two pointer개념을 사용하기는 하지만 pivot을 기점으로 물리적으로 분리된 공간에 실제로 데이터를 swap하는 것이 보였으나, 여기 방식에 따르면 일단 한쪽 끝 (아래 코드는 end)으로 피벗을 배치시킨 뒤에 pivot보다 작은 원소의 개수를 카운트 하고 incremental 하게 위치를 잡는 것을 볼 수 있다.
맨 마지막 줄이 중요한데, 피벗의 위치는 아직 끝이므로 본래 있어야 할 자리로 옮기는 것을 알 수 있다.
#include <random>
#include <utility>
static std::mt19937 engine{std::random_device{}()};
static std::uniform_int_distribution<unsigned int> generator{};
template <typename Iter, class Less>
Iter partition(Iter begin, Iter end, Less const &less) {
auto pivot = begin + generator(engine) % (end - begin);
std::swap(*pivot, *(end - 1));
pivot = end - 1; // ==IMPORTANT== pivot is currently end of the sequence
size_t count = 0; // pivot보다 작은 원소의 개수를 카운트
for (auto cur = begin; cur != pivot; ++cur) {
if (less(*cur, *pivot)) {
// move element to left
// begin ~ begin + count => *pivot 보다 작은 원소들
// begin+count ~ cur => *pivot 보다 크거나 같은 원소들
std::swap(*cur, *(begin + count));
count += 1;
}
}
// move pivot to right place
std::swap(*pivot, *(begin + count));
return begin + count;
}
template <typename Iter, class Less>
void sort(Iter begin, Iter end, Less const &less) {
if (end - begin <= 1) {
return;
}
auto mid = partition(begin, end, less);
sort(begin, mid, less);
sort(mid + 1, end, less);
}
pseudocode (python)
from typing import MutableSequence, Callable
from random import randint
def partition(ls: MutableSequence, lo: int, hi: int, less: Callable[[int, int], bool]):
pivot_idx = randint(lo, hi - 1)
# move pivot last of the element
ls[pivot_idx], ls[hi - 1] = ls[hi - 1], ls[pivot_idx]
pivot_idx = hi - 1
count = 0 # count will be the separating point between less(x, pivot) and other
for i in range(lo, pivot_idx):
# iterate EXCEPT pivot
if less(ls[i], ls[pivot_idx]):
ls[i], ls[lo + count] = ls[lo + count], ls[i]
count += 1
# move pivot to the right place
ls[pivot_idx], ls[lo + count] = ls[lo + count], ls[pivot_idx]
return lo + count
def qsort(ls: MutableSequence, lo: int, hi: int, less: Callable[[int, int], bool]):
"""
- lo: starting index (inclusive)
- hi: end index (exclusive)
- less: function that can customize ordering
"""
if hi - lo <= 1:
return
pivot = partition(ls, lo, hi, less)
qsort(ls, lo, pivot, less)
qsort(ls, pivot + 1, hi, less) # pivot은 넣으면 무한재귀